/*************************************************************************
	> File Name: 001.AVL_Tree.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 四  2/18 17:20:40 2021
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int key;
    int height;
    struct Node *lchild, *rchild;
} Node;

Node __NIL;
#define NIL (&__NIL)

void initNIL() {
    NIL->key = 0;
    NIL->height = 0;
    NIL->lchild = NIL->rchild = NIL;
    return ;
}

Node *getNewNode(int key) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->key = key;
    p->height = 1;
    p->lchild = p->rchild = NIL;
    return p;
}

void update_height(Node *root) {
    root->height = (root->lchild->height > root->rchild->height ? root->lchild->height : root->rchild->height) + 1;
    return ;
}

Node *left_rotate(Node *root) {
    Node *temp = root->rchild;
    root->rchild = temp->lchild;
    temp->lchild = root;
    update_height(root);
    update_height(temp);
    return temp;
}

Node *right_rotate(Node *root) {
    Node *temp = root->lchild;
    root->lchild = temp->rchild;
    temp->rchild = root;
    update_height(root);
    update_height(temp);
    return temp;
}

Node *maintain(Node *root) {
    if (abs(root->lchild->height - root->rchild->height) <= 1) return root;
    if (root->lchild->height > root->rchild->height) {
        if (root->lchild->lchild->height < root->lchild->rchild->height) {
            root->lchild = left_rotate(root->lchild);
        }
        root = right_rotate(root);
    } else {
        if (root->rchild->rchild->height < root->rchild->lchild->height) {
            root->rchild = right_rotate(root->rchild);
        }
        root = left_rotate(root);
    }
    return root;
}

Node *insert(Node *root, int val) {
    if (root == NIL) return getNewNode(val);
    if (val == root->key) return root;
    if (val < root->key) root->lchild = insert(root->lchild, val);
    else root->rchild = insert(root->rchild, val);
    update_height(root);
    return maintain(root);
}

Node *predecessor(Node *root) {
    Node *temp = root->lchild;
    while (temp->rchild) temp = temp->rchild;
    return temp;
}

Node *erase(Node *root, int val) {
    if (root == NIL) return NIL;
    if (val < root->key) root->lchild = erase(root->lchild, val);
    else if (val > root->key) root->rchild = erase(root->rchild, val);
    else {
        if (root->lchild == NIL || root->rchild == NIL) {
            Node *temp = root->lchild != NIL ? root->lchild : root->rchild;
            free(root);
            return temp;
        } else {
            Node *temp = predecessor(root);
            root->key = temp->key;
            root->lchild = erase(root->lchild, temp->key);
        }
    }
    update_height(root);
    return maintain(root);
}

int search(Node *root, int val) {
    if (root == NIL) return -1;
    if (val == root->key) return 1;
    if (val < root->key) return search(root->lchild, val);
    return search(root->rchild, val);
}

void clear(Node *root) {
    if (root == NIL) return ;
    clear(root->lchild);
    clear(root->rchild);
    free(root);
    return ;
}

void print(Node *root) {
    printf("(%d[%d], %d, %d)\n", root->key, root->height, root->lchild->key, root->rchild->key);
}

void preorder_tranversal(Node *root) {
    if (root == NIL) return ;
    print(root);
    preorder_tranversal(root->lchild);
    preorder_tranversal(root->rchild);
    return ;
}

int main() {
    initNIL();
    int op, val;
    Node *root = NIL;
    while (~scanf("%d%d", &op, &val)) {
        switch (op) {
            case 0: printf("Search %d, result: %d\n", val, search(root, val)); break;
            case 1: root = insert(root, val); break;
            case 2: root = erase(root, val); break;
        }
        if (op) preorder_tranversal(root);
    }
    return 0;
}
